﻿using System;
using System.Diagnostics;

namespace ConsoleApplication16
{
    struct Unit<T1, T2>
    {
        public readonly T1 Value;
        public readonly T2 Next;

        public Unit(T1 value, T2 next)
        {
            Value = value;
            Next = next;
        }
    }

    class Unit
    {
        public static Unit<T1, T2> Create<T1, T2>(T1 item1, T2 item2)
        {
            return new Unit<T1, T2>(item1, item2);
        }
    }

    internal class FibonacciProgram
    {
        public static void Main2()
        {
            var stopwatch = new Stopwatch();
            stopwatch.Start();
            for (var i = 0; i < 1000; i++) Last5_2(40000);
            stopwatch.Stop();
            Console.WriteLine(stopwatch.ElapsedMilliseconds);
        }

        public static int Last5_2(int number)
        {
            if (number < 0) throw new Exception();
            return F2_2(1, 1).Skip(number - 1)().Value;
        }

        private static Chain<int> F2_2(int a, int b)
        {
            return () => Unit.Create(b, F2_2(b, (a + b) % 100000));
        }

        private static int F2(int counter, int a, int b)
        {
            if (counter == 0) return a;
            return
                F2(counter - 1, b, (a + b)%100000);
        }

        public static int Last5(int number)
        {
            if (number < 0) throw new Exception();
            return F2(number, 1, 1);
        }
    }
}